struct cmp
{
    bool operator()(pair<int, vector<int>> p1, pair<int, vector<int>> p2)
    {
        return p1.first < p2.first;
    }
};

class Solution {
public:
    vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
        vector<vector<int>> results;

        priority_queue<pair<int, vector<int>> ,vector<pair<int, vector<int>>>, cmp> heap;

        int sum = 0;
        for(int i = 0; i < nums1.size(); i++)
        {
            for(int j = 0; j < nums2.size(); j++)
            {
                sum = nums1[i]+nums2[j];
                heap.push({sum, {nums1[i], nums2[j]}});
                if(heap.size() > k)
                {
                    heap.pop();
                }
            }
        }

        while(!heap.empty())
        {
            results.push_back(heap.top().second);
            heap.pop();
        }

        return results;
    }
};
